package jianzhi;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * description:
 * author:张腾
 * date:2021-06-22
 */

/**
 * 输入一个字符串，打印出该字符串中字符的所有排列。
 * 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素
 */
public class jianzhi38 {
    public static void main(String[] args) {
        String[] abcs = new jianzhi38().permutation("dkjphedy");
        for (String abc : abcs) {
            System.out.println(abc);
        }
    }

    List<String> res = new ArrayList<>();
    boolean[] flag ;
    public String[] permutation(String s) {
        char[] words = s.toCharArray();
        //保证字符串中有重复字符时只会加入一次
        Arrays.sort(words);
        flag = new boolean[words.length];
        StringBuffer sb = new StringBuffer();
        dfs(words,words.length,0,sb);
        String[] result = new String[res.size()];
        for (int i = 0; i < result.length; i++) {
            result[i] = res.get(i);
        }
        return result;
    }

    private void dfs(char[] words, int len, int depth, StringBuffer s) {

        if (depth==len){

            res.add(s.toString());

            return;
        }

        for (int i  = 0;i < len;i++){
            if (flag[i] || (i>0 && !flag[i-1] && words[i]==words[i-1])) continue;

            s.append(words[i]);
            flag[i] = true;
            dfs(words,len,depth+1,s);
            flag[i] = false;
            s.deleteCharAt(s.length()-1);

        }
    }
}
